/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main_divide_and_conquer.c
*   创 建 者：baichao
*   创建日期：2024年01月03日
*   描    述：
*
================================================================*/

/*
 * 给你一个整数数组 nums
 * ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 *
 * 示例 1：
 *   输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 *   输出：6
 *   解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 * 示例 2：
 *   输入：nums = [1]
 *   输出：1
 *
 * 示例 3：
 *   输入：nums = [5,4,-1,7,8]
 *   输出：23
 *
 * 提示：
 *   1 <= nums.length <= 105
 *   -104 <= nums[i] <= 104
 *
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 */

#include <limits.h>
#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int maxCrossingSum(int* nums, int low, int mid, int high) {
  int left_sum = INT_MIN;
  int sum = 0;

  for (int i = mid; i >= low; i--) {
    sum += nums[i];
    if (sum > left_sum) {
      left_sum = sum;
    }
  }

  int right_sum = INT_MIN;
  sum = 0;

  for (int i = mid + 1; i <= high; i++) {
    sum += nums[i];
    if (sum > right_sum) {
      right_sum = sum;
    }
  }

  return left_sum + right_sum;
}

int maxSubArraySum(int* nums, int low, int high) {
  if (low == high) {
    return nums[low];
  }

  int mid = (low + high) / 2;

  int left_sum = maxSubArraySum(nums, low, mid);
  int right_sum = maxSubArraySum(nums, mid + 1, high);
  int cross_sum = maxCrossingSum(nums, low, mid, high);

  return max(max(left_sum, right_sum), cross_sum);
}

int maxSubArray(int* nums, int numsSize) {
  return maxSubArraySum(nums, 0, numsSize - 1);
}

int main() {
  int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  int numsSize = sizeof(nums) / sizeof(nums[0]);

  int result = maxSubArray(nums, numsSize);
  printf("Maximum sum of a subarray: %d\n", result);

  return 0;
}
